import collections


class Solution:
    _MOD = 10 ** 9 + 7

    # O(N)
    # 乘法逆元、数学

    def makeStringSorted(self, s: str) -> int:
        size = len(s)

        # 阶乘：factorials[i] = i! mod m
        factorials = [0] * (size + 1)

        # 阶乘的乘法逆元：factorials_inverse[i] = i! 在 mod m 意义下的乘法逆元
        factorials_inverse = [0] * (size + 1)

        factorials[0] = 1
        factorials_inverse[0] = 1
        for i in range(1, size):
            factorials[i] = factorials[i - 1] * i % self._MOD
            factorials_inverse[i] = pow(factorials[i], self._MOD - 2, self._MOD)

        count = collections.Counter(s)

        ans = 0
        for i in range(size - 1):
            # 求出比s[i]小的字符总数
            rank = sum(num for ch, num in count.items() if ch < s[i])

            # 计算排列的分子
            cur = rank * factorials[size - i - 1] % self._MOD

            # 计算排列的分母，并逐个乘乘法逆元
            for ch, num in count.items():
                cur *= factorials_inverse[num] % self._MOD

            ans += cur

            count[s[i]] -= 1

        return ans % self._MOD


if __name__ == "__main__":
    print(Solution().makeStringSorted("cba"))  # 5
    print(Solution().makeStringSorted("aabaa"))  # 2
    print(Solution().makeStringSorted("cdbea"))  # 63
    print(Solution().makeStringSorted("leetcodeleetcodeleetcode"))  # 982157772

    # 测试用例13
    print(Solution().makeStringSorted("ppjsumufzmralrmefzicsbecynemkjjqnoxsjhbhpsqgyhstxlmwuhpxkd"))

    # 自制用例
    print(Solution().makeStringSorted("leetcode"))  # 4660
    print(Solution().makeStringSorted("leetcodeleetcode"))  # 624849580
